package dfs;

import java.util.*;

/**
 * @author pengfei.hpf
 * @date 2020/2/13
 * @verdion 1.0.0
 */
public class AccountsMerge {
    public List<List<String>> accountsMerge(List<List<String>> accounts){
        List<List<String>> res = new ArrayList<>();
        if(accounts == null || accounts.size() <1){
            return res;
        }
        Map<String, String> emailToName = new HashMap<>();
        Map<String, List<String>> graph = new HashMap<>();
        for(List<String> list: accounts){
            String name = "";
            for(String email: list){
                if(name.equals("")){
                    name = email;
                    continue;
                }
                graph.computeIfAbsent(email, x->new ArrayList<String>()).add(list.get(1));
                graph.computeIfAbsent(list.get(1), x->new ArrayList<String>()).add(email);
                emailToName.put(email, name);
            }
        }
        Set<String> visited = new HashSet<>();
        for(String email: graph.keySet()){
            if(!visited.contains(email)){
                List<String> emails = new ArrayList<String>();
                dfs(graph, visited, emails, email);
                emails.add(0, emailToName.get(email));
                res.add(emails);
            }
        }
        return res;
    }

    private void dfs(Map<String, List<String>> graph, Set<String> visited, List<String> emails, String email){
        if(visited.contains(email)){
            return;
        }
        emails.add(email);
        visited.add(email);
        List<String> list = graph.get(email);
        for(String e: list){
            dfs(graph, visited, emails, e);
        }
    }
}
